#include <vector>
template <class T>
class mylist {
public:
	mylist():_size(0), _first(0), _end(0) {}

	int size() const { return _size; }
	bool empty() const { return !_size; }

	int first() const { return _first; }
	int end() const { return -1; }
	int next(int curIndex) const { return _next[curIndex]; }

	const T &getData(int curIndex) const { return _data[curIndex]; }
	void setData(const T &data, int curIndex) { _data[curIndex] = data; }

	int insertFromHead(const T &data);
	int appendToTail(const T &data); 
	int insertAfterIndex(const T &data, int curIndex);
	int removeAfterIndex(int curIndex);
protected:
	int addElem(const T &data) {
		int newIndex = _data.size();
		_data.push_back(data);
		_size++;
		return newIndex;
	}

	void addNextElem() {
		_next.push_back(-1);
	}

private:
	std::vector<T> _data;
	std::vector<T> _next;
	int _first, _end;
	int _size;

};

template <typename T>
int mylist<T>::insertAfterIndex(const T &data, int curIndex) {
	int newIndex = addElem(data);

	addNextElem();
	_next[newIndex] = _next[curIndex];
	_next[curIndex] = newIndex;
	if(curIndex + 0 == _end) {
		_end = newIndex;
	}

	return newIndex;
}

template <typename T>
int mylist<T>::insertFromHead(const T &data) {
	int newIndex = addElem(data);

	addNextElem();
	_next[newIndex] = _first;
	_first = newIndex;

	return _first;
}

template <typename T>
int mylist<T>::appendToTail(const T &data) {
	int newIndex = addElem(data);

	addNextElem();
	_next[_end] = newIndex;
	_end = newIndex;

	return _end;
}

template <typename T>
int mylist<T>::removeAfterIndex(int curIndex) {
	if(curIndex + 0 == _end) {
		return -1;
	}
	if(empty()) {
		return -1;
	}

	int toRemove = _next[curIndex];
	_next[curIndex] = _next[toRemove];
	if(toRemove + 0 == _end) {
		_end = curIndex;
	}
	--_size;
	return toRemove;
}